package com.lw.leetcode.str.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * b
 * str
 * 2564. 子字符串异或查询
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/12 17:06
 */
public class SubstringXorQueries {

    public static void main(String[] args) {
        SubstringXorQueries test = new SubstringXorQueries();

        // [[0,2],[2,3]]
        String str = "101101";
        int[][] arr = {{0, 5}, {1, 2}};

        int[][] ints = test.substringXorQueries(str, arr);
        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }
    }

    public int[][] substringXorQueries(String s, int[][] queries) {
        int size = s.length();
        Map<Integer, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        int o = -1;
        int z = -1;
        for (int i = 0; i < size; i++) {
            if (chars[i] == '1') {
                if (o == -1) {
                    o = i;
                }
            } else {
                if (z == -1) {
                    z = i;
                }
            }
            if (o != -1 && z != -1) {
                break;
            }
        }
        if (z != -1) {
            map.put(0, z);
        }
        if (o != -1) {
            map.put(1, o);
            int limit = Math.min(size - o, 31);
            int item = 1;
            int f = 1;
            for (int i = 1; i < limit; i++) {
                int end = o + i;
                item = (item << 1) + chars[end] - '0';
                f = (f << 1) + 1;
                Integer c = map.get(item);
                if (c == null || c > end - i) {
                    map.put(item, end - i);
                }
                end++;
                int it = item;
                while (end < size) {
                    it = (it << 1) + chars[end] - '0';
                    it = it & f;
                    if (chars[end - i] == '1') {
                        c = map.get(it);
                        if (c == null || c > end - i) {
                            map.put(it, end - i);
                        }
                    }
                    end++;
                }
            }
        }
        int length = queries.length;
        int[][] values = new int[length][2];
        for (int i = 0; i < length; i++) {
            int[] query = queries[i];
            int[] value = values[i];
            int t = query[0] ^ query[1];
            Integer c = map.get(t);
            if (c != null) {
                value[0] = c;
                value[1] = c + Integer.toBinaryString(t).length() - 1;
            } else {
                value[0] = -1;
                value[1] = -1;
            }
        }
        return values;
    }

}
